#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//for (int j = 0; j < gap; j++)
		//{
			for (int i = 0; i < n - gap; i++)
			{
				int end = i;
				int tem = a[end + gap];
				while (end >= 0)
				{
					if (tem < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tem;
			}
		//}
	}
	
	
	
}
int main()
{
	int a[] = { 42,53,4,56,7,43,34,23,3353,525,23523,2535,45,36,7457 };
	ShellSort(a, 15);
	for (int i = 0; i < 15; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}